package com.study.lihan.letcode;

import java.util.*;

/*https://leetcode-cn.com/problems/valid-parentheses/
* */
public class My20 {
    public static void main(String[] args) {
       String s = "]";
        Solution20 solution20 = new Solution20();
        boolean result = solution20.myisValid(s);
        System.out.println("结果是:"+result);
    }
}


class Solution20 {
    public boolean myisValid(String s) {
        if(s ==null) return false;

        Map<Character ,Character > keyAndVal = new HashMap<>();
        keyAndVal.put(')','(');
        keyAndVal.put('}','{');
        keyAndVal.put(']','[');
        Stack<Character > stack = new Stack<>();
        for(int i=0,len = s.length(); i<len; i++){
          char temp = s.charAt(i);
            if(!keyAndVal.containsKey(temp)){
                stack.push(temp);
                continue;
            }
           if( stack.isEmpty() || keyAndVal.get(temp)!=stack.pop())return  false;
        }
         return  stack.isEmpty();
    }
    public boolean isValid(String s) {
        Deque<Character> deque = new LinkedList<>();
        char ch;
        for (int i = 0; i < s.length(); i++) {
            ch = s.charAt(i);
            //碰到左括号，就把相应的右括号入栈
            if (ch == '(') {
                deque.push(')');
            }else if (ch == '{') {
                deque.push('}');
            }else if (ch == '[') {
                deque.push(']');
            } else if (deque.isEmpty() || deque.peek() != ch) {
                return false;
            }else {//如果是右括号判断是否和栈顶元素匹配
                deque.pop();
            }
        }
        //最后判断栈中元素是否匹配
        return deque.isEmpty();
    }
}